1. Field of the Invention
The present invention relates generally to methods and systems for data compression. More specifically, the present invention describes methods and systems for signal prediction in predictive coding.
2. Description of the Related Art
In predictive coding, instead of coding the source symbol directly, the encoder first generates a predictor of the signal symbol to be coded and computes the prediction error, i.e., the difference between the source symbol and its predictor, then encodes only the prediction error and sends the codeword to the decoder. The decoder decodes the received codeword to obtain the prediction error and performs the same prediction operation at the encoder to generate the same predictor. The decoder then reconstructs the symbol by adding the decoded prediction error to the predictor. To predict the current symbol, the encoder uses the previously decoded symbols to generate a predictor.
Predictive coding is widely used in many applications, especially those involving video, audio, and other media signals. FIG. 1 illustrates a conventional predictive encoder 100, with a comparator 102, an encoder 104, a decoder 108, and a storage device 106. When the source to be encoded is video, it generally contains motion. Predictive coding is usually used in conjunction with motion estimation and transform coding to provide an efficient video coding technique, that is called “motion-compensated predictive coding.” Examples of such techniques include those developed by the Motion Picture Experts Group (MPEG) of the International Organization for Standards (ISO), the H.26x techniques developed by the International Telecommunications Union (ITU), and the like.
In motion-compensated predictive coding of a video frame, an encoder first performs motion estimation. The motion estimation searches one or more reference frames to find the best match between the block of the source signals, in this case, a block of pixels to be coded in the current frame and a block of pixels in the reference frame. The reference frames are usually the previously reconstructed frames so that the same references are also available at the decoder. The best matching block has the minimum differential error compared to the block to be coded in terms of a pre-selected error measure, for example the mean squared error (MSE) or the sum of absolute difference (SAD). This minimum error, or “residue,” is called “the motion-compensated prediction error.”
Also, the differences between the coordinates of the block to be coded in the current frame and its best matching block in the reference frame form a coordinate displacement vector called a motion vector mv=(mvx, myy), where mvx, myy indicate the block's horizontal displacement and vertical displacement, respectively. As mentioned above, the motion-compensated prediction error is usually compressed using transform coding. The motion-compensated prediction error is transformed into a frequency domain representation, e.g., Discrete Cosine Transform (DCT) for better compression performance. Quantization and entropy coding are then performed on the frequency coefficients, and the motion vector is also coded and transmitted to the decoder. In decoding, the decoder first decodes the received signal to recover the prediction error and motion vectors by performing entropy decoding, inverse quantization, inverse DCT, etc., then uses the motion vector to find the corresponding predictor (the best match) from the reference frame(s) and adds it to the decoded prediction error.
FIG. 2 illustrates a conventional predictive video encoding system 200. The system 200 includes a comparator 202, an encoder 204, a motion estimator 206, a motion-compensated predictor 208, a frame storage 210, and a decoder 212.
The motion estimator 206 receives a current frame Pn and at least one previously reconstructed frame as the reference frame and determines a motion vector, mv=(mvx,mvy), which indicates the differences in horizontal and vertical coordinates of a pixel block in a reference image and a corresponding pixel block in the image being encoded.
The motion-compensated predictor 208 receives the motion vector, mv, from the motion estimator 206, and also receives one or more reference frames from the frame storage 210 to provide a motion-compensated prediction for the pixel values. The motion-compensated prediction from the motion-compensated predictor 208 is compared to the current pixel value by a comparator 202 to provide a motion-compensated prediction error signal En.
An encoder 204, then encodes the prediction error En and the motion vector mv to provide the output signal.
A decoder 212 emulates the decoding process at the receiver so that both encoder and decoder have exactly the same reconstructed frames as the reference frames. It decodes the coded signal from the encoder 204 and provides the decoded output signal to frame storage 210, which will be used by the motion estimator 206 and the motion-compensated predictor 208 to provide a reference for the next frame.
In general, the performance of predictive coding largely depends on the prediction scheme. For example, for video coding, the performance depends largely on the motion-compensated prediction scheme to produce the minimum prediction errors.
The conventional methods and systems for predictive coding only work well when there is strong statistical correlation in the source symbols. If the correlation is weak, then the prediction will not be able to effectively predict the next source symbol to be encoded and result in large prediction errors and poor performance.
Furthermore, there is usually noise existing in the source and the transmission channel. The compression itself will also cause quantization noise. When there is noise in the reference signal that is used as the predictor or when the next signal symbol to be encoded itself is contaminated with noise, the conventional methods and systems of predictive coding do not have the ability to correct or reduce the errors caused by noises and oftentimes fail to effectively predict the signal symbol to be encoded. This results in large prediction error and, therefore, poor coding performance. In this manner, these issues adversely affect the ability of conventional predictive coders to compress a signal.